The search for truth

How do we know when something is true?

We are convinced by a persuasive argument!
What is the basis of persuasion?
- Trust in the source
- Consensus of peers
- Sound reasoning based on facts we already know to be true

Logic

Given a premise, we want to reach a valid conclusion.
In other words, we want to derive new facts using facts we already know.

We want to make an argument supporting our conclusion without resorting to:
- Our reputation or expertise
- How many other people agree
- Intimidation

Origins

Logic is one of the oldest intellectual disciplines, dating back to Aristotle

Aristotle’s logic focuses on the idea of deduction.

Deduction (as defined by Aristotle):: A statement where, given certain assumptions, something different from these assumptions is also necessarily true.

Origins

Subject : The objects we talk about in a statement

Predicate : What we say about the subject

Syllogism : Three statements where the subject of the first is the predicate of the second, and the third statement is implied by the first two.

Origins

All men are mortal
Socrates is a man
Socrates is mortal

Origins

All men are mortal
Socrates is a man
Socrates is mortal

Proposition : A statement that is either true or false.

Modern logic

In 1879 Gottlob Frege’s publishes Begriffsschrift
- Roughly translated as: “Concept Writing”.
Frege introduces formal notation, some still used ( $⊢$ ).
Defines a propositional calculus in terms of
- 9 axioms (statements assumed to be true)
- 3 inference rules (rules that create new statements from existing ones)

Propositional calculus

p := "You are a bird."
q := "You have wings."

Compound statements:

If you are a bird, you have wings: $p ⟹ q$
You cannot be a bird and not have wings: $\neg (p \land \neg q)$
But bats have wings and are not birds! Is this a counterexample?

How do we prove $p ⟹ q$ is false?

p := "??? is a bird."
q := "??? has wings."

A counter example to $p ⟹ q$ requires $p$ to be true and $q$ to be false: $p \land \neg q$ .

In other words, is there a bird without wings?
- According to birds.cornell.edu, all birds have two wings, so we probably won’t find a counterexample…
- …without a time machine. Moa’s, the only known wingless bird went extinct ~500 years ago.

$p ⟹ q$ is not $q ⟹ p$ !!!

p := "??? is a bird."
q := "??? has wings."

Bats are not birds, but have wings: $\neg p \land q$

To contradict $p ⟹ q$ , we would need $p \land \neg q$ .
$p ⟹ q$ $\approx$ “If you are a bird, you have wings.”
$q ⟹ p$ $\approx$ “If you have wings, you are a bird.”
Bats are a counterexample to
$q ⟹ p$ , but not $p ⟹ q$ .

Examples from Alice in Wonderland

“I say what I mean.”

“I see what I eat.”

“I like what I get.”

“I breathe when I sleep.”

$\neq$
(why?)

“I mean what I say.”

“I eat what I see.”

“I get what I like.”

“I sleep when I breathe.”

Predicate calculus

Bertrand Russell (Master Bertie) reintroduced Aristotle’s distinction between subject and predicate
Some cats do not have fur: $\exists cat . HasNoFur (cat)$
- “There exists a subject (in the set of all cats), call it $cat$ , such that $HasNoFur (cat)$ is true.”
- $HasNoFur (\cdot)$ is a predicate that is true when the subject it applies to ( $cat$ ) does not have fur.
All men are mortal: $\forall man . IsMortal (man)$
- “For any subject (from the set of all men), call it $man$ , $IsMortal (man)$ is true.”
- $IsMortal (\cdot)$ is a predicate that is true when the subject it applies to ( $man$ ) is mortal.

What would Bertie do?

Is this inference correct?

All X are Y
Some Y are Z
Therefore, some X are Z

Try X=Toyotas, Y=Japanese cars, and Z=made in America
- All Toyotas are Japanese cars
- Some Japanese cars are made in America
- Therefore, some Toyotas are made in America
Now try X=Toyotas, Y=cars, and Z=Fiats
- All Toyotas are cars
- Some cars are Fiats
- Therefore, some Toyotas are Fiats

What would Bertie do?

Is this inference correct? No! This rule is unsound!!

All X are Y
Some X are Z
Therefore, some X are Z

Try X=Toyotas, Y=Japanese cars, and Z=made in America
- All Toyotas are Japanese cars
- Some Japanese cars are made in America
- Therefore, some Toyotas are made in America
Now try X=Toyotas, Y=cars, and Z=Fiats
- All Toyotas are cars
- Some cars are Fiats
- Therefore, some Toyotas are Fiats

Proofs are truth-preserving arguments

We need to create new propositions from given facts.
A sound rule of inference should only create true conclusions.
A proof, given a set of premises, is just a sequence of sentences where each element is
- A premise, OR
- The result of applying a sound rule of inference to earlier members in the sequence
- Once the desired conclusion is added to the sequence, the proof is complete!

What is logic? (informally, but big words)

Axioms : Propositions that you assume to be true. Ideally, truths that are self-evident.

Rules of inference : Rules that create new propositions from axioms or other inferred propositions.

Some special names for inferred (proven to be true) propositions:

Lemma: A statement used to prove other statements
Theorem: A new statement that is “important”
Corollary: A special case of a theorem that is useful/popular

Using previously proven Lemmas, Theorems, and Corollaries (plus axioms), new results can be proven with rules of inference.

Propositional logic

Outline

The Language of Propositions
- Connectives
- Truth Values

Applications
- Translating English Sentences
- System Specifications
- Logic Puzzles
- Logic Circuits

Logical Equivalences
- Important Equivalences
- Showing Equivalence
- Satisfiability

Proposition or Not?

A proposition is a declarative sentence that is either true or false.

Sentence:

Trenton is the capital of New Jersey.

The Moon is made of green cheese.

Sit down!

1 + 0 = 1

What time is it?

0 + 0 = 2

x + 1 = 2

Propositional Logic

Notation for constructing propositions

The proposition that is always true: $T$
The proposition that is always false: $F$

Propositional variables: p, q, r, s
- may be true or false

Logical connectives
- Used to construct compound propositions
- Negation $\neg$
- Conjunction $\land$
- Disjunction $\lor$
- Implication $\to$
- Biconditional $\leftrightarrow$

Truth tables

We can specify the meaning of connectives using truth tables.

Truth table: A table with the truth-values of a logical formula for each combination of values of its propositional variables.

Truth tables were invented by Ludwig Wittgenstein, a student of Russell’s…

who once alledgedly threatened Karl Popper (another philosopher) with a fireplace poker.

Negation

The negation of a proposition $p$ is written $\neg p$ and has truth table:

$p$	$\neg p$
$T$	$F$
$F$	$T$

Example: If $p$ denotes “The earth is round.”, then $\neg p$ denotes “It is not the case that the earth is round.”, or just “The earth is not round.”

Conjunction

The conjunction of propositions $p$ and $q$ is written $p \land q$ and has truth table:

$p$	$q$	$p \land q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$F$
$F$	$F$	$F$

Example: If $p$ denotes “I am at home.” and $q$ denotes “It is raining.” then $p \land q$ denotes “I am home, and it is raining.”

Disjunction

The disjunction of propositions $p$ and $q$ is written $p \lor q$ and has truth table:

$p$	$q$	$p \land q$
$T$	$T$	$T$
$T$	$F$	$T$
$F$	$T$	$T$
$F$	$F$	$F$

Example: If $p$ denotes “I am at home.” and $q$ denotes “It is raining.” then $p \lor q$ denotes “I am home, or it is raining.”

English “or” vs logical “or”

In English, “or” has two distinct meanings.

Inclusive Or : “Students who have taken MATH 19A or MATH 19B may take this class.”
- Meaning: Students should have taken one of the pre-reqs, but may have taken both.

Exclusive Or : “The entree comes with soup or salad.”
- Meaning: You can get a soup or a salad with the entree, but not both.

Which kind of “or” is disjunction? ( $p \lor q$ )

Exclusive or (XOr)

The exclusive or of propositions $p$ and $q$ is written $p \oplus q$ and has truth table:

$p$	$q$	$p \oplus q$
$T$	$T$	$F$
$T$	$F$	$T$
$F$	$T$	$T$
$F$	$F$	$F$

Example: If $p$ denotes “I choose the soup.” and $q$ denotes “I choose the salad.” then $p \oplus q$ denotes “I choose the soup or I choose the salad.”

Conditional reasoning

Assume the following premise is true:
- “If I study hard, I will pass CSE 16.”

Can we infer
- “If I passed CSE 16, then I studied hard.” ?

Conditional reasoning

Assume the following premise is true:
- “If the company is convicted of fraud, it will go bankrupt.”

Suppose the company goes bankrupt. Can we infer the company was convicted of fraud?

Implication

The implication of proposition $p$ with respect to $q$ is written $p \to q$ and has truth table:

$p$	$q$	$p \to q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$???$
$F$	$F$	$???$

Example: If $p$ denotes “I am at home.” and $q$ denotes “It is raining.” then $p \to q$ denotes “If I am home, then it is raining.”

If I am at home and it is raining, then $p \to q$ is true.
If I am at home and it is not raining, then $p \to q$ is false.

What if I am not at home?

Implication

The implication of proposition $p$ with respect to $q$ is written $p \to q$ and has truth table:

$p$	$q$	$p \to q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$???$
$F$	$F$	$???$

Example: If $x > 2$ then $x^{2} > 4$ .

More formally, let $P (x) = x > 2$ and $Q (x) = x^{2} > 4$ . Is $P (x) \to Q (x)$ true for any $x$ ?
- What if $x = 1$ ? $P (1)$ is false and $Q (1)$ is false.
- What if $x = - 5$ ? $P (- 5)$ is false and $Q (- 5)$ is true.

Implication

The implication of proposition $p$ with respect to $q$ is written $p \to q$ and has truth table:

$p$	$q$	$p \to q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$T$
$F$	$F$	$T$

Example: If $x > 2$ then $x^{2} > 4$ .

We say that $P (x) \to Q (x)$ is true since you will never find a value of $x$ such that $x > 2$ and $x^{2} < 4$ .
Therefore in the truth table, whenever $p$ is false, $p \to q$ is true, regardless of the value of $q$ .

Implication $\neq$ causation

“If I use the power of Grayskull to make it true, then $1 + 1 = 2$ .”

Intuitively, this statement seems false, or at least fishy.
- $1 + 1 = 2$ is true by the laws of math, not by the power of Grayskull.

Mathematically, the statement is true.
- The requirement is to prove the conclusion true, whether we use the premise or not is irrelevant.
- So say the line, He-Man: “By the power of Grayskull, 1+1=2!”

Implication as a promise

You could view the logical conditional as an obligation.
- “If I am elected, then I will fund affordable housing.”

If the politician is elected and does not fund affordable housing, then they have broken their campaign pledge.
- In this case $p = T$ (“I am elected.”), but $q = F$ (“I did not fund affordable housing.”).

If the politician is not elected then no promises are broken.

Understanding implication

In $p \to q$ there doesn’t need to be any connection between the antecedent ( $p$ ) or the consequent ( $q$ ).
The “meaning” of $p \to q$ only depends on the truth values of $p$ and $q$ .

Recognizing implication

All of these are ways of expressing $p \to q$ :

if $p$ then $q$

if $p$ , $q$

$q$ , unless $\neg p$

$q$ if $p$

$q$ whenever $p$

$q$ follows from $p$

$p$ implies $q$

$q$ only if $p$

$q$ when $p$

$p$ is sufficient for $q$

$q$ is necessary for $p$

a sufficient condition for $q$ is $p$

a necessary condition for $p$ is $q$

Recognizing implication

Write as an implication $p \to q$
- What are $p$ and $q$ ?

Why does he want to know $q$ when $\neg p$ ?

$p$ : “You want to hang out.”
$q$ : “I will be in your city.”
$p \to q$ ?

Biconditional

If $p$ and $q$ are propositions, the we can form the biconditional proposition $p \leftrightarrow q$ , read as “ $p$ if and only if $q$ ”, with truth table:

$p$	$q$	$p \leftrightarrow q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$F$
$F$	$F$	$T$

Example: If $p$ denotes “I am at home.” and $q$ denotes “It is raining.” then $p \leftrightarrow q$ denotes “I am home if and only if it is raining.”

Recognizing biconditionals

Ways of expressing $p \leftrightarrow q$ :

$p$ if and only if $q$

$p$ is necessary and sufficient for $q$

if $p$ then $q$ , and conversely

$p$ iff $q$

Should you honk if their light is green?

If you honk, then you love formal logic.

If you love formal logic, then you honk.

Tautologies and contradictions

Tautology: a proposition that is always true.

Example: $p \lor \neg p$

Contradiction: a proposition that is always false.

Example: $p \land \neg p$

$p$	$\neg p$	$p \lor \neg p$	$p \land \neg p$
$T$	$F$	$T$	$F$
$F$	$T$	$T$	$F$

Converse, inverse, contrapositive

Converse: The converse of $p \to q$ is $q \to p$ .

Inverse: The inverse of $p \to q$ is $\neg p \to \neg q$ .

Contrapositive: The contrapositive of $p \to q$ is $\neg q \to \neg p$ .

$p$	$q$	$p \to q$	$q \to p$	$\neg p \to \neg q$	$\neg q \to \neg p$ .
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$T$	$T$	$F$
$F$	$T$	$T$	$F$	$F$	$T$
$F$	$F$	$T$	$T$	$T$	$T$

Converse, inverse, contrapositive

Notice anything about that last column (the contrapositive)?

It had the same values as $p \to q$ !

That means the contrapositive of $p \to q$ is logically equivalent!

Truth tables are a good way to show logical equivalence (and non-equivalence). Which of the below formulas are equivalent?

$p$	$q$	$p \to q$	$\neg q \to \neg p$	$\neg p \lor q$	$q \to p$
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$F$	$F$	$T$
$F$	$T$	$T$	$T$	$T$	$F$
$F$	$F$	$T$	$F$	$F$	$T$

Logical equivalence

Logically equivalent: Two propositions $p$ and $q$ are logically equivalent iff $p \leftrightarrow q$ is a tautology.

We write equivalence as $P \Leftrightarrow Q$ or $P \equiv Q$ where $P$ and $Q$ are compound propositions.
If $P$ and $Q$ ’s truth tables agree, they are equivalent!

$p$	$q$	$p \to q$	$\neg q \to \neg p$	$\neg p \lor q$	$q \to p$
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$F$	$F$	$T$
$F$	$T$	$T$	$T$	$T$	$F$
$F$	$F$	$T$	$F$	$F$	$T$

Proving De Morgan’s Second Law

De Morgan’s Second Law: $\neg (p \land q) \equiv \neg p \lor \neg q$ $\neg (p \lor q) \equiv \neg p \land \neg q$

Let’s prove it!

$p$	$q$	$\neg (p \land q)$	$\neg p \lor \neg q$	$\neg (p \lor q)$	$\neg p \land \neg q$
$T$	$T$	$F$	$F$	$F$	$F$
$T$	$F$	$T$	$T$	$F$	$F$
$F$	$T$	$T$	$T$	$F$	$F$
$F$	$F$	$T$	$T$	$T$	$T$

Laws of propositional logic

We fully can axiomatize (specify the axioms / assumptions of) propositional logic using similar equivalences.

Idempotence	$p \lor p \equiv p$	$p \land p \equiv p$
Associativity	$(p \lor q) \lor r \equiv p \lor (q \lor r)$	$(p \land q) \land r \equiv p \land (q \land r)$
Commutativity	$p \lor q \equiv q \lor p$	$p \land q \equiv q \land p$
Distributivity	$p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$	$p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$
Identity	$p \lor F \equiv p$	$p \land T \equiv T$
Domination	$p \land F \equiv F$	$p \lor T \equiv T$
Dbl negation	$\neg \neg p \equiv p$
Complement	$p \land \neg p \equiv F$ $\neg T \equiv F$	$p \lor \neg p \equiv T$ $\neg F \equiv T$
De Morgans	$\neg (p \lor q) \equiv \neg p \land \neg q$	$\neg (p \land q) \equiv \neg p \lor \neg q$
Absorption	$p \lor (p \land q) \equiv p$	$p \land (p \lor q) \equiv p$
Conditional identity	$p \to q \equiv \neg p \lor q$	$p \leftrightarrow q \equiv (p \to q) \land (q \to p)$

Predicates and quantifiers

Generalizing relationships between propositions

Propositional example:

If Jack knows Jill, then Jill knows Jack.
- Jack knows Jill.
- Does Jill know Jack?

What about other people?
- If Calvin knows Hobbes, then Hobbes knows Calvin.
- If Charlie knows Lucy, then Lucy knows Charlie.
- …

How can we say “If one person knows another, then the second person knows the first.” without needing a proposition for every person?

Predicate logic

Predicate logic adds new features to propositional logic:

Variables: $x$ , $y$ , $z$
Predicates: “ $x$ is even”, “ $x^{n} + y^{n}$ = z^n”
Propositional functions: $P (x)$ , $M (x, y, z)$
Quantifiers: $\forall$ “for all”, $\exists$ “there exists”

Defining propositional functions

Predicate: A logical statement whose truth value depends on one or more variables.

Domain: The set of all possible values for a variable.

Propositional function: A generalization of a proposition defined by a predicate which becomes a proposition when the predicate’s variables are replaced by elements from their domain.

Defining propositional functions

Example: Let the domain of $x$ be the integers. $P (x) := x > 0$

$P (- 3)$ is false.
$P (0)$ is true.
$P (3)$ is true.
$P (x)$ is not a proposition.
$P (z)$ is not a proposition.

Quantifiers

Quantifiers let us talk about all or some (i.e., at least one) of the elements in a variable’s domain.

Around since Frege, but notation and popularization due mostly to his contemporary Peirce.

Charles Peirce (1839-1914)

Universal quantification: $\forall$

Universal quantification: $\forall x . P (x)$ reads “For all $x$ , $P$ of $x$ .” and asserts that $P (x)$ is true for every $x$ in the domain.

Example: Let the domain of $x$ be the integers.

Let $P (x) := | x | \geq 0$ $\forall x . P (x) is true.$

Let $P (x) := x \geq 0$ $\forall x . P (x) is false.$

Existential quantification: $\exists$

Existential quantification: $\exists x . P (x)$ reads “There exists an $x$ such that $P$ of $x$ .” and asserts that $P (x)$ is true for at least one $x$ in the domain.

Example: Let the domain of $x$ be the integers.

Let $P (x) := x \geq 0$ $\exists x . P (x) is true.$

Let $P (x) := | x | < 0$ $\exists x . P (x) is false.$

Uniqueness quantification: $\exists!$

Uniqueness quantification: $\exists! x . P (x)$ reads “There is a unique $x$ such that $P$ of $x$ .” and asserts that $P (x)$ is true for one and only one $x$ in the domain.

Example: Let the domain of $x$ be the integers.

Let $P (x) := x + 1 = 0$ $\exists! x . P (x) is true.$

Let $P (x) := x + 1 \leq 0$ $\exists! x . P (x) is false.$

Uniqueness quantification: $\exists!$

Uniqueness quantification: $\exists! x . P (x)$ reads “There is a unique $x$ such that $P$ of $x$ .” and asserts that $P (x)$ is true for one and only one $x$ in the domain.

Uniqueness is actually derivable in terms of $\forall$ , $\exists$ , and equality ( $=$ ). $\exists! x . P (x) \equiv \exists x . (P (x) \land \forall y . P (y) \to y = x)$

Variable scope

Variables have a scope just like in a programming language.

In predicate logic, the scope of a variable is defined by a quantifier.

Occurrences of a variable within a quantifier’s scope are called bound. Occurrences which are not bound are called free.

Example: $\exists y . P (x, y)$ Here $x$ is free and $y$ is bound.

Quantifier intuition

One way to understand quantifiers is to think about the finite case.

Let’s assume the domain of $x$ is finite and consider how we might evaluate the truth value of $\forall x . P (x)$
1. Loop through all possible values of $x$ .
2. If $P (x)$ is true for each value of $x$ , then $\forall x . P (x)$ is true.
3. Otherwise $\forall x . P (x)$ is false.
Similar to a list of ANDs, one for each value of $x$ $(P (x_{0}) \land P (x_{1}) \land . . .)$

Quantifier intuition

One way to understand quantifiers is to think about the finite case.

Let’s assume the domain of $x$ is finite and consider how we might evaluate the truth value of $\exists x . P (x)$
1. Loop through all possible values of $x$ .
2. If $P (x)$ is false for each value of $x$ , then $\exists x . P (x)$ is false.
3. Otherwise $\exists x . P (x)$ is true.
Similar to a list of ORs, one for each value of $x$ $(P (x_{0}) \lor P (x_{1}) \lor . . .)$

Negating quantified statements

Notice how our algorithms seemed similar, but opposite to each other? These equivalences make that explicit:

$\neg \forall x . P (x) \equiv \exists x . \neg P (x)$

$\neg \exists x . P (x) \equiv \forall x . \neg P (x)$

To get why, think about De Morgan’s Law:

$\neg (P (x_{0}) \land P (x_{1}) \land . . .) \equiv (\neg P (x_{0}) \lor \neg P (x_{1}) \lor . . .)$

$\neg (P (x_{0}) \lor P (x_{1}) \lor . . .) \equiv (\neg P (x_{0}) \land \neg P (x_{1}) \land . . .)$

Recognizing quantification

“Every student in the class has taken a Python course.”
- Domain?
- Formal statement?

Define $P (x)$ to be “ $x$ has taken a Python course.” where the domain of $x$ is the set of students in the class. $\forall x . P (x)$

Negating the statement gives “Is it not the case that every student in the class has taken Python.” $\neg \forall x . P (x)$

Or put another way, “There is a student in the class who has not taken Python.” $\exists x . \neg P (x)$

Recognizing quantification

“There is a student in the class who has taken a Python course.”

$\exists x . P (x)$

Negating the statement gives “it not the case that there is a student in the class who has taken a Python course.” $\neg \exists x . P (x)$

Or put another way, “Every student in the class has not taken a Python course.” $\forall x . \neg P (x)$

Nested quantifiers

Nested quantifiers are often necessary to express concepts.

Example: “Every real number has an inverse.”

$\forall x \exists y . (x + y = 0)$

Propositional functions can also be nested:
- Let $Q (x) := \exists y . P (x, y)$
- Let $P (x, y) := x + y = 0$

$\forall x . Q (x)$

Order of quantifiers

Is $\exists y \forall x$ the same as $\forall x \exists y$ ?

Consider $P (x, y) := y$ is a soul mate of $x$ .

Translate to English: $\exists y . \forall x . P (x, y)$
- “There exists a $y$ that is the soulmate of every $x$ .”
Translate to English: $\forall x . \exists y . P (x, y)$
- “For every $x$ there exists a $y$ that is the soulmate of $x$ .”
Translate to English: $\forall x . \exists! y . P (x, y)$
- “For every $x$ there exists a unique $y$ that is the soulmate of $x$ .”

Order of quantifiers

Examples:

Let $P (x, y) := x + y = y + x$ , where the domain of $x$ and $y$ is the real numbers. $\forall x \forall y . P (x, y) \equiv ? \forall y \forall x . P (x, y)$
- Yes!
Let $Q (x, y) := x + y = 0$ , where the domain of $x$ and $y$ is the real numbers. $\forall x \exists y . Q (x, y) \equiv ? \exists y \forall x . Q (x, y)$
- No!

More quantifier order practice

Let $P (x, y) := x \cdot y = 0$ where $x$ and $y$ are real numbers.

$\forall x . \forall y . P (x, y)$
- Answer: False
$\forall x . \exists y . P (x, y)$
- Answer: True
$\exists x . \forall y . P (x, y)$
- Answer: True
$\exists x . \exists y . P (x, y)$
- Answer: True

More quantifier order practice

Let $P (x, y) := x / y = 1$ where $x$ and $y$ are real numbers.

$\forall x . \forall y . P (x, y)$
- Answer: False
$\forall x . \exists y . P (x, y)$
- Answer: False
$\exists x . \forall y . P (x, y)$
- Answer: False
$\exists x . \exists y . P (x, y)$
- Answer: True

Recognizing nested quantification

Statement	Statement is true	Statement is false
$\forall x \forall y . P (x, y)$ $\forall y \forall x . P (x, y)$	$P (x, y)$ is true for every pair $x, y$ .	There is at least on pair $x, y$ for which $P (x, y)$ is false.
$\forall x \exists y . P (x, y)$	For every $x$ there is a $y$ for which $P (x, y)$ is true.	There is an $x$ such that $P (x, y)$ is false for every $y$ .
$\exists x \forall y . P (x, y)$	There is an $x$ for which $P (x, y)$ is true for every $y$ .	For every $x$ there is a $y$ for which $P (x, y)$ is false.
$\exists x \exists y . P (x, y)$ $\exists y \exists x . P (x, y)$	There is a pair $x, y$ for which $P (x, y)$ is true.	$P (x, y)$ is false for every pair $x, y$

Negating nested quantification

Recall De Morgan’s laws for quantifiers:

$\neg \forall x . P (x) \equiv \exists x . \neg P (x)$

$\neg \exists x . P (x) \equiv \forall x . \neg P (x)$

Let’s apply these laws to a statement with nested quantifiers.

Write a statement for “There does not exist a person who has taken a flight on every airline in the world.”
- Let $P (p, f) :=$ “ $p$ has taken flight $f$ ”, where $p$ has domain people, and $f$ has domain flights.
- Let $Q (f, a) :=$ “Flight $f$ is operated by $a$ .”, where $a$ has domain airlines, and $f$ has domain flights.

$\neg \exists p . \forall a . \exists f . P (p, f) \land Q (f, a)$

Negating nested quantification

Now let’s use De Morgan’s Laws to move the negation as far “inwards” as possible.

$\neg \exists p . \forall a . \exists f . P (p, f) \land Q (f, a)$
$\forall p . \neg \forall a . \exists f . P (p, f) \land Q (f, a)$ by De Morgan’s for $\exists$
$\forall p . \exists a . \neg \exists f . P (p, f) \land Q (f, a)$ by De Morgan’s for $\forall$
$\forall p . \exists a . \forall f . \neg (P (p, f) \land Q (f, a))$ by De Morgan’s for $\exists$
$\forall p . \exists a . \forall f . \neg P (p, f) \lor \neg Q (f, a)$ by De Morgan’s for $\exists$

#5 in English?

“For every person there is an airline such that for all flights, the person has not taken that flight or that flight is not on that airline.”

More translation practice

Example:

Let $x, y, z$ have domain of the students in your school.

Let $C (x) :=$ “ $x$ has a computer.”

Let $F (x, y) :=$ “ $x$ and $y$ are friends.”

Translate: $\forall x . C (x) \lor (\exists y . C (y) \land F (x, y))$
- Answer: “Every student in your school has a computer or has a friend who has a computer.”
Translate: $\exists x . \forall y . \forall z . (F (x, y) \land F (x, z) \land (y \neq z)) \to \neg F (y, z)$
- Answer: “There is a student with no friends that are also friends with each other.”

More translation practice

Example 1: “Brothers are siblings.”
- Solution: $\forall x . \forall y . (B (x, y) \to S (x, y))$
Example 2: “Siblinghood is symmetric.”
- Solution: $\forall x . \forall y . (S (x, y) \to S (y, x))$
Example 3: “Everybody loves somebody.”
- Solution: $\forall x . \exists y . L (x, y)$
Example 4: “There is someone who is loved by everyone.”
- Solution: $\exists y . \forall x . L (x, y)$
Example 5: “There is someone who loves someone.”
- Solution: $\exists x . \exists y . L (x, y)$
Example 6: “Everyone loves themselves”
- Solution: $\forall x . L (x, x)$

Translating mathematical statements

Example: Translate “The sum of two positive integers is always positive” into an expression in predicate logic.

Solution:

Rewrite to make quantifiers and domains explicit:
- “For every two integers, if these integers are both positive, then the sum of the integers is positive.”
Rewrite to use variables and specify their domain:
- “For all positive integers $x$ and $y$ , $x + y$ is positive.”
Now replace the English phrases with the appropriate notation.
- $\forall x . \forall y . (x > 0 \land y > 0) \to (x + y > 0)$ where $x, y$ have domain of (all) integers.

Example from Calculus (of infinitesimals):

Limit: Let $f$ be a function defined on some open interval that contains the number $a$ , except possibly at $a$ itself. Then we say that the limit of $f (x)$ as $x$ approaches $a$ is $L$ , and we write
$lim_{x \to a} f (x) = L$ if for every number $ε > 0$ there is a number $δ > 0$ such that $if 0 < | x - a | < δ then | f (x) - L | < ε$

We can use quantifiers to express the definition of the limit of a real-valued function $f (x)$ of a real variable $x$ at a point $a$ in its domain.

$\forall ε . \exists δ . \forall x . (0 < | x - a | < δ \to | f (x) - L | < ε)$

where the domain of $ε$ and $δ$ is the positive reals and the domain of $x$ is all reals.

Reasoning about Calculus with logic

How could we use our logical definition of limits to express that the limit of $f (x)$ as $x$ approaches $a$ does not exist?

We need to say that for all real numbers $L$ , $\neg \forall ε . \exists δ . \forall x . (0 < | x - a | < δ \to | f (x) - L | < ε)$

Move the negation in
- $\equiv \exists ε . \neg \exists δ . \forall x . (0 < | x - a | < δ \to | f (x) - L | < ε)$
- $\equiv \exists ε . \forall δ . \neg \forall x . (0 < | x - a | < δ \to | f (x) - L | < ε)$
- $\equiv \exists ε . \forall δ . \exists x . \neg (0 < | x - a | < δ \to | f (x) - L | < ε)$
- $\equiv \exists ε . \forall δ . \exists x . \neg (\neg (0 < | x - a | < δ) \lor | f (x) - L | < ε)$
- $\equiv \exists ε . \forall δ . \exists x . 0 < | x - a | < δ \land \neg (| f (x) - L | < ε)$
- $\equiv \exists ε . \forall δ . \exists x . 0 < | x - a | < δ \land | f (x) - L | \geq ε$

Reasoning about Calculus with logic

Quantify over all real numbers $L$ :
- $\forall L . \exists ε . \forall δ . \exists x . 0 < | x - a | < δ \land | f (x) - L | \geq ε$

Translating back to English:
- For every real number $L$ , there is a real number $ε > 0$ , such that for every real number $δ > 0$ , there exists a real number $x$ such that $0 < | x - a | < δ$ and $| f (x) - L | \geq ε$ .

Logical reasoning

Recap

Tautology: a proposition that is always true.

Example: $p \lor \neg p$

Contradiction: a proposition that is always false.

Example: $p \land \neg p$

Logically equivalent: Two propositions $p$ and $q$ are logically equivalent, written $p \equiv q$ , iff $p \leftrightarrow q$ is a tautology.

Proof technique

So far we have only proven tautologies, contradictions, and equivalence using truth tables. This approach is not scalable.

With $n$ variables, there are $2^{n}$ truth assignments. Worse, truth tables cannot be used with quantifiers and infinite sets!

$p$	$q$	$r$
$T$	$T$	$T$
$T$	$T$	$F$
$T$	$F$	$T$
$T$	$F$	$F$
$F$	$T$	$T$
$F$	$T$	$F$
$F$	$F$	$T$
$F$	$F$	$F$

Deriving new propositions from existing ones

How can we get new conclusions from existing premises without enumerating all truth values?

IDEA: Can we manipulate logical statements symbolically using axioms and inference rules to obtain a proof of the desired conclusion?

Proofs according to Logicomix

A proof is the verification of a a mathematical statement starting from a set of agreed-upon first principles proceeding by unambiguous and unabridged logical steps or rules of inference.

What are agreed-upon first principles?
- Axioms or proven statements derived from these axioms.

Theorems

Theorem: any inference obtained from

a set of premises: $Γ$
axioms or previously proven theorems
the rules of inference

Notation:

$Γ ⊢ α$
$⊢ α$ (no premises, $Γ$ is empty)
Zybook style: $\frac{Γ}{∴ α}$

Zybook also calls theorems valid arguments.

Example: Hilbert’s system

Small set of axioms and rules of inference from which all theorems can be derived.

Three axioms:
(actually 4 originally, but one turned out to be redundant) $\begin{aligned} A 1 & : α \to (β \to α) \\ A 2 & : (α \to (β \to γ)) \to ((α \to β) \to (α \to γ)) \\ A 3 & : (\neg α \to \neg β) \to (β \to α) \end{aligned}$

One inference rule: Modus Ponens $p, p \to q ⊢ q$

From which all theorems of propositional logic can be derived!

Hilbert’s Axioms are tautologies!

Can you prove it?

$α$	$β$	$β \to α$	$α \to (β \to α)$
$T$	$T$	$T$	$T$
$T$	$F$	$F$	$T$
$F$	$T$	$T$	$T$
$F$	$F$	$T$	$T$

Prove an axiom?

Wondering how they figured out one of the axioms was redundant?

They proved it could be derived from the other axioms!

$\begin{aligned} A 1 & : α \to (β \to α) \\ A 2 & : (α \to (β \to γ)) \to ((α \to β) \to (α \to γ)) \\ A 3 & : (\neg α \to \neg β) \to (β \to α) \end{aligned}$

Goal: Derive $⊢ α \to α$ using only axioms and modus ponens.

$\begin{aligned} (1) & p \to ((q \to p) \to p) \\ A1 with α = p and β = (q \to p) . \\ (2) & (p \to ((q \to p) \to p) \to ((p \to (q \to p)) \to (p \to p))) \\ A2 with α = p and β = (q \to p) and γ = p . \\ (3) & (p \to (q \to p)) \to (p \to p) \\ modus ponens using (1) and (2) \\ (4) & (p \to (q \to p)) \\ A1 with α = p and β = q \\ p \to p \\ modus ponens using (3) and (4) \end{aligned}$

Prove an inference rule?

Show it is a valid argument (is a theorem)!

Consider this argument: $α \to β, β \to γ ⊢ α \to γ$

What do we need to prove to show this argument is a theorem?

In general $p_{0}, . . ., p_{n} ⊢ q$ is valid (true for all truth values of $p_{i}$ and $q$ ) if $(p_{0} \land . . . \land p_{n}) \to q$ is a tautology.

Proof

$α \to β, β \to γ ⊢ α \to γ$

$\begin{aligned} A 1 & : α \to (β \to α) \\ A 2 & : (α \to (β \to γ)) \to ((α \to β) \to (α \to γ)) \\ A 3 & : (\neg α \to \neg β) \to (β \to α) \end{aligned}$

$\begin{aligned} (1) & β \to γ & Premise \\ (2) & (β \to γ) \to (α \to (β \to γ)) & A1 \\ (3) & α \to (β \to γ) & MP w/ (1),(2) \\ (4) & (α \to (β \to γ)) \to ((α \to β) \to (α \to γ)) & A2 \\ (5) & (α \to β) \to (α \to γ) & MP w/ (3),(4) \\ (6) & α \to β & Premise \\ (7) & α \to γ & MP w/ (5),(6) \end{aligned}$

Notice: Every line is either a premise, an instance of an axiom, or the result of applying a theorem or rule (e.g., MP) to previous line(s).

Some valid (and useful) rules

Rule	Name
$p, p \to q ⊢ q$	Modus ponens
$\neg q, p \to q ⊢ \neg p$	Modus tollens
$q ⊢ p \lor q$	Addition (L)
$p ⊢ p \lor q$	Addition (R)
$p \land q ⊢ p$	Simplification (L)
$p \land q ⊢ q$	Simplification (R)
$p, q ⊢ p \land q$	Conjunction
$p \to q, q \to r ⊢ p \to r$	Hypothetical syllogism
$p \lor q, \neg p ⊢ q$	Disjunctive syllogism
$p \lor q, \neg p \lor r ⊢ q \lor r$	Resolution

Back to Aristotle

What about quantifiers?

We can express Aristotle’s example $^{*}$ in predicate logic as the following argument:

$\begin{matrix} \begin{matrix} \forall x . Human (x) \to Mortal (x) & Human (Socrates) \end{matrix} \\ ∴ Mortal (Socrates) \end{matrix}$

or

$\forall x . Human (x) \to Mortal (x), Human (Socrates) ⊢ Mortal (Socrates)$

Is this a valid argument?

$*$ : updated to be slightly less gender-biased

Universal Instantiation (UI)

$\begin{matrix} \begin{matrix} \forall x . P (x) \end{matrix} \\ ∴ P (c) \end{matrix}$

$\forall x . P (x) ⊢ P (c)$

where $c$ is from the domain of $x$ .

Example: For the domain of all dogs, where Thornton is a dog.

Suppose “All dogs are cuddly.”
Therefore, “Thornton is cuddly.”

Universal Generalization (UG)

$\begin{matrix} \begin{matrix} P (c) \end{matrix} \\ ∴ \forall x . P (x) \end{matrix}$

$P (c) ⊢ \forall x . P (x)$

where $c$ is an arbitrary element from the domain of $x$ .

This is often left implicit in proofs when a statement has been proven in terms of an arbitrary element.

Example: Consider an arbitrary natural number $n$ .

$n \geq 0$ (by definition)
Therefore, $\forall x . x \geq 0$

Existential Instantiation (EI)

$\begin{matrix} \begin{matrix} \exists x . P (x) \end{matrix} \\ ∴ P (c) \end{matrix}$

$P (c) ⊢ \exists x . P (x)$

for some element $c$ in the domain of $x$
(but you don’t know which one).

Example:

“There is someone who got a ticket to Taylor Swift.”
Let’s call them TayFan and say: “TayFan got a ticket.”

“There is someone who got 2 tickets to Taylor Swift.”
Can we say “TayFan got 2 tickets.”?
No, because it may or may not be the same person.
Instead we call this one TayFan2 and say “TayFan2 got 2 tickets.”

Existential Generalization (EG)

$\begin{matrix} \begin{matrix} P (c) \end{matrix} \\ ∴ \exists x . P (x) \end{matrix}$

$P (c) ⊢ \exists x . P (x)$

for some element $c$ in the domain of $x$
(but you may or may not know which one).

Example:

“Michelle got tickets to Taylor Swift.”
“Therefore, someone got tickets to Taylor Swift.”

Michelle would sometimes be called the “witness” to the existential since her existence proves the quantified statement.

Back to Socrates’ Mortality

$\begin{matrix} \begin{matrix} \forall x . Human (x) \to Mortal (x) & Human (Socrates) \end{matrix} \\ ∴ Mortal (Socrates) \end{matrix}$

$\begin{aligned} \forall x . Human (x) \to Mortal (x) & (1) & Premise \\ Human (Socrates) \to Mortal (Socrates) & (2) & UI, (1) \\ Human (Socrates) & (3) & Premise \\ Mortal (Socrates) & MP, (3), (2) \end{aligned}$

$\begin{matrix} \begin{matrix} \begin{matrix} \begin{matrix} \forall x . Human (x) \to Mortal (x) \end{matrix} \\ Human (Socrates) \to Mortal (Socrates) \end{matrix} (UI) & Human (Socrates) \end{matrix} \\ ∴ Mortal (Socrates) \end{matrix} (MP)$

More practice

Example: Suppose:

“A student in the class has not read the book.”
“Everyone in the class passed the exam.”

Construct a valid argument (prove) that the following conclusion follows from these premises.

Solution:

Define:

$C (x)$ to be “ $x$ is in the class.”
$B (x)$ to be “ $x$ has read the book.”
$P (x)$ to be “ $x$ passed the exam.”

More practice

Formally, we wish to prove $\begin{matrix} \begin{matrix} \exists x . C (x) \land \neg B (x) & \forall x . C (x) \to P (x) \end{matrix} \\ ∴ \exists x . P (x) \land \neg B (x) \end{matrix}$

$\begin{aligned} (1) & \exists x . C (x) \land \neg B (x) & Premise \\ (2) & C (a) \land \neg B (a) & EI on (1) \\ (3) & C (a) & Simplification (L) on (2) \\ (4) & \forall x . C (x) \to P (x) & Premise \\ (5) & C (a) \to P (a) & UI on (4) \\ (6) & P (a) & MP from (3) and (5) \\ (7) & \neg B (a) & Simplification (R) on (2) \\ (8) & P (a) \land \neg B (a) & Conjunction on (6) and (7) \\ (9) & \exists x . P (x) \land \neg B (x) & EG from (8) \end{aligned}$

Proof tree version

$\begin{matrix} \begin{matrix} \begin{matrix} \begin{matrix} \begin{matrix} \begin{matrix} \begin{matrix} \begin{matrix} \begin{matrix} \begin{matrix} \exists x . C (x) \land \neg B (x) \end{matrix} \\ C (a) \land \neg B (a) \end{matrix} (EI) \end{matrix} \\ C (a) \end{matrix} (Simpl) & \begin{matrix} \begin{matrix} \forall x . C (x) \to P (x) \end{matrix} \\ C (a) \to P (a) \end{matrix} (UI) \end{matrix} \\ P (a) \end{matrix} (MP) & \begin{matrix} \begin{matrix} \begin{matrix} \begin{matrix} \exists x . C (x) \land \neg B (x) \end{matrix} \\ P (a) \land \neg B (a) \end{matrix} (EI) \end{matrix} \\ \neg B (a) \end{matrix} (Simpl) \end{matrix} \\ P (a) \land \neg B (a) \end{matrix} (Conj) \end{matrix} \\ \exists x . P (x) \land \neg B (x) \end{matrix} (EG)$

Valid Quantifier Rules

Rule	Condition	Name
$\forall x . P (x) ⊢ P (c)$	$c$ is an element in domain of $P$	Universal Instantiation
$P (c) ⊢ \forall x . P (x)$	$c$ is an arbitrary element in domain of $P$	Universal Generalization
$\exists x . P (x) ⊢ P (c)$	$c$ is a “fresh” name for some particular element in domain of $P$	Existential Instantiation
$P (c) ⊢ \exists x . P (x)$	$c$ is a particular element in domain of $P$	Existential Generalization

$p$	$q$	$p \to q$	$q \to p$	$\neg p \to \neg q$	$\neg q \to \neg p$ .
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$T$	$T$	$F$
$F$	$T$	$T$	$F$	$F$	$T$
$F$	$F$	$T$	$T$	$T$	$T$

$p$	$q$	$p \to q$	$\neg q \to \neg p$	$\neg p \lor q$	$q \to p$
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$F$	$F$	$T$
$F$	$T$	$T$	$T$	$T$	$F$
$F$	$F$	$T$	$F$	$F$	$T$

$p$	$q$	$p \to q$	$\neg q \to \neg p$	$\neg p \lor q$	$q \to p$
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$F$	$F$	$T$
$F$	$T$	$T$	$T$	$T$	$F$
$F$	$F$	$T$	$F$	$F$	$T$

$p$	$q$	$\neg (p \land q)$	$\neg p \lor \neg q$	$\neg (p \lor q)$	$\neg p \land \neg q$
$T$	$T$	$F$	$F$	$F$	$F$
$T$	$F$	$T$	$T$	$F$	$F$
$F$	$T$	$T$	$T$	$F$	$F$
$F$	$F$	$T$	$T$	$T$	$T$

$p$	$q$	$r$
$T$	$T$	$T$
$T$	$T$	$F$
$T$	$F$	$T$
$T$	$F$	$F$
$F$	$T$	$T$
$F$	$T$	$F$
$F$	$F$	$T$
$F$	$F$	$F$

$p$	$q$	$p \to q$	$q \to p$	$\neg p \to \neg q$	$\neg q \to \neg p$ .
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$T$	$T$	$F$
$F$	$T$	$T$	$F$	$F$	$T$
$F$	$F$	$T$	$T$	$T$	$T$

$p$	$q$	$p \to q$	$\neg q \to \neg p$	$\neg p \lor q$	$q \to p$
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$F$	$F$	$T$
$F$	$T$	$T$	$T$	$T$	$F$
$F$	$F$	$T$	$F$	$F$	$T$

$p$	$q$	$p \to q$	$\neg q \to \neg p$	$\neg p \lor q$	$q \to p$
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$F$	$F$	$T$
$F$	$T$	$T$	$T$	$T$	$F$
$F$	$F$	$T$	$F$	$F$	$T$

$p$	$q$	$\neg (p \land q)$	$\neg p \lor \neg q$	$\neg (p \lor q)$	$\neg p \land \neg q$
$T$	$T$	$F$	$F$	$F$	$F$
$T$	$F$	$T$	$T$	$F$	$F$
$F$	$T$	$T$	$T$	$F$	$F$
$F$	$F$	$T$	$T$	$T$	$T$

$p$	$q$	$r$
$T$	$T$	$T$
$T$	$T$	$F$
$T$	$F$	$T$
$T$	$F$	$F$
$F$	$T$	$T$
$F$	$T$	$F$
$F$	$F$	$T$
$F$	$F$	$F$

$p$	$q$	$p \to q$	$q \to p$	$\neg p \to \neg q$	$\neg q \to \neg p$ .
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$T$	$T$	$F$
$F$	$T$	$T$	$F$	$F$	$T$
$F$	$F$	$T$	$T$	$T$	$T$

$p$	$q$	$p \to q$	$\neg q \to \neg p$	$\neg p \lor q$	$q \to p$
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$F$	$F$	$T$
$F$	$T$	$T$	$T$	$T$	$F$
$F$	$F$	$T$	$F$	$F$	$T$

$p$	$q$	$p \to q$	$\neg q \to \neg p$	$\neg p \lor q$	$q \to p$
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$F$	$F$	$T$
$F$	$T$	$T$	$T$	$T$	$F$
$F$	$F$	$T$	$F$	$F$	$T$

$p$	$q$	$\neg (p \land q)$	$\neg p \lor \neg q$	$\neg (p \lor q)$	$\neg p \land \neg q$
$T$	$T$	$F$	$F$	$F$	$F$
$T$	$F$	$T$	$T$	$F$	$F$
$F$	$T$	$T$	$T$	$F$	$F$
$F$	$F$	$T$	$T$	$T$	$T$

$p$	$q$	$r$
$T$	$T$	$T$
$T$	$T$	$F$
$T$	$F$	$T$
$T$	$F$	$F$
$F$	$T$	$T$
$F$	$T$	$F$
$F$	$F$	$T$
$F$	$F$	$F$